package offer.offer03;

import java.util.*;

/**
 * 6, 100, 很土的办法, 从前到后, 遇到不一样的点就加到set里, 遇到重复的, 就set清零, 然后从该点从后向前找最大的不重复的串;
 */
public class Solution48 {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        String[] strList = s.split("");
        System.out.println(Arrays.toString(strList));
        System.out.println("原字符串长: " + s.length());
        Set<String> strSet = new HashSet<>();
        int maxLen = 0;
        int maxLen2 = 0;//临时maxLen
        for(int i = 0; i < s.length(); i++){
            String curStr = strList[i];
            if(!strSet.contains(curStr)){
                strSet.add(curStr);
                maxLen2 ++;
                if(maxLen2 > maxLen) maxLen = maxLen2;
            }else {
                //遇到重复的, 从后往前找一下相同的点
                strSet.clear();
                maxLen2 = 0;
                for(int j = i; j >= 0; j--){
                    if(!strSet.contains(strList[j])){
                        strSet.add(strList[j]);
                        maxLen2++;
                    }else break;
                }
            }
        }
        return maxLen;
    }
    /**
     * 动态规划 + 哈希表
     * 这个使用map, 就用键值对的方式把位置存下来了, 妙哇, 相当于匹配的时候自然就知道了上一个字母在哪里
     * Character, char的包装类, 忘了包装类这种东西了。
     */
    public int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i, 即上一次出现当前字符的位置
            // 更新哈希表, 即这个哈希表里有当前值之前的每一个char的最后一次出现的位置
            dic.put(s.charAt(j), j);
            //这个是以当前字母为结尾的最大长度
            //当tmp比j-i小的时候, 说明当前点上一次出现的时候, 在上一次循环的子串之外, 给tmp+1,
            //当tmp比j-i大的时候, 说明当前点的上一次出现在子串之内, 所以当前点结尾的最大子串长为j-i;
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }

    /**
     * 每一次都从后往前找第一个与当前点相同的char, 相当于上面的的在HashMap中存着最后一次出现的位置
     */
    public int lengthOfLongestSubstring3(String s) {
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = j - 1;
            while(i >= 0 && s.charAt(i) != s.charAt(j)) i--; // 线性查找 i
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }

    public static void main(String[] args) {
        String input = new String("dvdf");
        System.out.println(new Solution48().lengthOfLongestSubstring(input));
    }
}
